/*
 * @Author: 缄默
 * @Date: 2021-11-15 20:10:04
 * @LastEditors: 缄默
 * @LastEditTime: 2021-11-15 20:28:12
 */

//统计和生成所有不同的二叉树

#include "../../DataStructure/tree.hpp"


int numTrees(int n);

int main() {

    cout << numTrees(3) << endl;
    return 0;
}

//返回数量 时间复杂度O(n)
int numTrees(int n) {
    if (n < 2) return 0;
    vector<int> num(n + 1, 0);
    num[0] = 1;
    for (int i = 1; i < num.size(); i++) {
        for (int j = 1; j < i + 1; j++) {
            num[i] += num[j - 1] * num[i - j];
        }
    }
    return num[n];
}

